#pragma once
#include <dialects/CFG/Dialect.h>
#include <dialects/CFG/Ops.h>
#include <dialects/CFG/TyAndProto.h>

#include <stack>
#include <unordered_set>
namespace lcir::cfg { 
// 将blockproto 拓扑排序
inline std::vector<BlockProto*> topologicalSort(BlockProto *entry) {
  // 使用bfs开始拓扑排序
  std::vector<BlockProto*> result;
  std::queue<BlockProto*> q;
  // std::map<BlockProto*, size_t>;
  q.push(entry);
  while (!q.empty()) {
    auto cur = q.front();
    result.push_back(cur);
    for (auto succ : cur->getSuccs()) {
      if (std::find(result.begin(), result.end(), succ) == result.end()) {
        q.push(succ);
      }
    }
    q.pop();
  }
  return result;
}
// 将blockproto逆后续排序
inline std::vector<BlockProto*> reversePostorderTraversal(BlockProto* entry) {
    std::unordered_set<BlockProto*> visited; // 用于记录已访问的节点
    std::vector<BlockProto*> stack; // 用于实现非递归遍历

    // 辅助函数，递归实现逆后续遍历
    std::function<void(BlockProto*)> traverse = [&](BlockProto* node) {
        if (visited.count(node) > 0) {
            return; // 如果已经访问过该节点，则返回
        }
        visited.insert(node);

        // 首先访问所有后继节点
        for (auto* succ : node->getSuccs()) {
            traverse(succ);
        }

        // 将当前节点压入栈中，这将在所有后继节点访问完毕后执行
        stack.push_back(node);
    };

    // 从入口节点开始遍历
    traverse(entry);

		std::vector<BlockProto*> rets;
    while (!stack.empty()) {
        BlockProto* node = stack.back();
        stack.pop_back();
        // 这里可以执行对节点的处理，例如打印节点信息
				rets.push_back(node);
    }
		return rets;
}

} // namespace lcir::cfg